package com.jay.structure.link;

/**
 * Created by caoyuan7 on 2018/12/11.
 */
class Link2
{
    public long dData;                  // data item
    public Link2 next;                   // next link in list
    // -------------------------------------------------------------
    public Link2(long dd)                // constructor
    { dData = dd; }
    // -------------------------------------------------------------
    public void displayLink2()           // display this link
    { System.out.print(dData + " "); }
}  // end class Link2
////////////////////////////////////////////////////////////////
public class SortedList
{
    private Link2 first;                 // ref to first item
    // -------------------------------------------------------------
    public SortedList()                 // constructor
    { first = null; }
    // -------------------------------------------------------------
    public boolean isEmpty()            // true if no links
    { return (first==null); }
    // -------------------------------------------------------------
    public void insert(long key)        // insert, in order
    {
        Link2 newLink2 = new Link2(key);    // make new link
        Link2 previous = null;            // start at first
        Link2 current = first;
        // until end of list,
        while(current != null && key > current.dData)
        {                             // or key > current,
            previous = current;
            current = current.next;       // go to next item
        }
        if(previous==null)               // at beginning of list
            first = newLink2;              // first --> newLink2
        else                             // not at beginning
            previous.next = newLink2;      // old prev --> newLink2
        newLink2.next = current;          // newLink2 --> old currnt
    }  // end insert()
    // -------------------------------------------------------------
    public Link2 remove()           // return & delete first link
    {                           // (assumes non-empty list)
        Link2 temp = first;               // save first
        first = first.next;              // delete first
        return temp;                     // return value
    }
    // -------------------------------------------------------------
    public void displayList()
    {
        System.out.print("List (first-->last): ");
        Link2 current = first;       // start at beginning of list
        while(current != null)      // until end of list,
        {
            current.displayLink2();   // print data
            current = current.next;  // move to next link
        }
        System.out.println("");
    }
}  // end class SortedList
////////////////////////////////////////////////////////////////
class SortedListApp
{
    public static void main(String[] args)
    {                            // create new list
        SortedList theSortedList = new SortedList();
        theSortedList.insert(20);    // insert 2 items
        theSortedList.insert(40);

        theSortedList.displayList(); // display list

        theSortedList.insert(10);    // insert 3 more items
        theSortedList.insert(30);
        theSortedList.insert(50);

        theSortedList.displayList(); // display list

        theSortedList.remove();      // remove an item

        theSortedList.displayList(); // display list
    }  // end main()
}  // end class SortedListApp